package com.hanxiaozhang.no3algorithm;

import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈单链表逆序〉
 * <p>
 * 总是忘记
 *
 * @author hanxinghua
 * @create 2023/12/4
 * @since 1.0.0
 */
public class No1SingleNodeReverse {


    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        println(head);
        Node pre = reverse3(head);
        println(pre);
    }


    private static void println(Node node) {
        while (node != null) {
            System.out.print(node.value);
            System.out.print(" ");
            node = node.next;
        }
        System.out.println("");
    }

    public static class Node {

        Integer value;

        Node next;

        public Node(Integer value) {
            this.value = value;
        }

        public Node(Integer value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }


    /**
     * 使用前继指针
     *
     * @param node
     * @return
     */
    private static Node reverse1(Node node) {

        if (node == null || node.next == null) {
            return node;
        }

        Node pre = null, next = null, cur = node;
        while (cur != null) {
            // 保存后继节点
            next = cur.next;
            // 后继节点指向前继
            cur.next = pre;
            // 移位
            pre = cur;
            cur = next;
        }
        // 不要忘记返回值
        return pre;
    }


    /**
     * 使用栈
     *
     * @param node
     * @return
     */
    private static Node reverse2(Node node) {

        if (node == null || node.next == null) {
            return node;
        }

        Stack<Node> stack = new Stack<>();
        while (node != null) {
            stack.push(node);
            node = node.next;
        }

        Node head = stack.pop();
        Node cur = head;
        while (!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        // 不要忘记最后一个节点设置成功空
        cur.next = null;
        // 不要忘记返回值
        return head;
    }


    /**
     * 使用递归逆序
     * 这个需要背的
     *
     * @param head
     * @return
     */
    public static Node reverse3(Node head) {

        if (head == null || head.next == null) {
            return head;
        }

        // 对链表中的剩余部分进行逆序
        Node reversed = reverse3(head.next);

        // 将当前节点追加到逆序后链表的末尾 Tips：背
        head.next.next = head;
        head.next = null;

        // Tips：背
        return reversed;
    }
}
